1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <cstdio>
#include <vector>
const int maxn = 5e5 + 5;
using namespace std;
int w[maxn], n, Q;
int s[maxn], top = 0;
vector <int> p[maxn];
vector <pair<int, int> > q[maxn];
struct T{
struct A{
int l, r, Max, v, lazy;
}a[maxn << 2];
void build(int cur, int l, int r){
a[cur].l = l, a[cur].r = r;
if (l == r){a[cur].v = w[l]; return;}
int mid = l + r >> 1;
build(cur << 1, l, mid);
build(cur << 1 | 1, mid + 1, r);
a[cur].v = max(a[cur << 1].v, a[cur << 1 | 1].v);
}
void pushdown(int cur){
if (!a[cur].lazy) return;
a[cur << 1].lazy = max(a[cur << 1].lazy, a[cur].lazy);
a[cur << 1].Max = max(a[cur << 1].Max, a[cur].lazy + a[cur << 1].v);
a[cur << 1 | 1].lazy = max(a[cur << 1 | 1].lazy, a[cur].lazy);
a[cur << 1 | 1].Max = max(a[cur << 1 | 1].Max, a[cur].lazy + a[cur << 1 | 1].v);
a[cur].lazy = 0;
}
void upd(int cur, int l, int r, int k){
if (a[cur].l > r || a[cur].r < l) return;
if (a[cur].l >= l && a[cur].r <= r){
a[cur].Max = max(a[cur].Max, a[cur].v + k);
a[cur].lazy = max(a[cur].lazy, k);
return;
}
pushdown(cur);
upd(cur << 1, l, r, k);
upd(cur << 1 | 1, l, r, k);
a[cur].Max = max(a[cur << 1].Max, a[cur << 1 | 1].Max);
}
int Query(int cur, int l, int r){
if (a[cur].l > r || a[cur].r < l) return 0;
if (a[cur].l >= l && a[cur].r <= r) return a[cur].Max;
pushdown(cur); return max(Query(cur << 1, l, r), Query(cur << 1 | 1, l, r));
}
}t; int ans[maxn];
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", w + i);
for (int i = 1; i <= n; i++){
while (top && w[s[top]] < w[i]) p[s[top--]].push_back(i);
p[s[top]].push_back(i); s[++top] = i;
} scanf("%d", &Q);
for (int l, r, i = 1; i <= Q; i++){
scanf("%d%d", &l, &r); q[l].push_back(make_pair(r, i));
} t.build(1, 1, n);
for (int i = n; i >= 1; i--){
for (int j = 0; j < p[i].size(); j++){
if (2 * p[i][j] - i <= n) t.upd(1, 2 * p[i][j] - i, n, w[i] + w[p[i][j]]);
}
for (int j = 0; j < q[i].size(); j++)
ans[q[i][j].second] = t.Query(1, i, q[i][j].first);
}
for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
return 0;
}
|